/*    Copyright 2010 Tobias Marschall
 *
 *    This file is part of MoSDi.
 *
 *    MoSDi is free software: you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation, either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    MoSDi is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with MoSDi.  If not, see <http://www.gnu.org/licenses/>.
 */

package mosdi.util;

public class Bits {

	public static class ValueAndBitLength {
		public long value;
		public int bits;
		public ValueAndBitLength(long value, int bits) {
			this.value = value;
			this.bits = bits;
		}
	}
	
	/** Transforms a given integer into Elias encoding, which is prefix-free. The encoded
	 *  value along with the number of used bits is returned. */
	public static ValueAndBitLength eliasEncode(long x) {
		if (x==0) return new ValueAndBitLength(0,1);
		boolean negative = x<0;
		int bitLength;
		if (negative) {
			x=-x;
			bitLength = 64 - Long.numberOfLeadingZeros(x); 
			if (bitLength>50) throw new IllegalArgumentException("Negative arguments must have a bit length <=50.");
		} else {
			bitLength = 64 - Long.numberOfLeadingZeros(x); 
			if (bitLength>51) throw new IllegalArgumentException("Argument must have a bit length <=51.");
		}
		// bit length of bit length of x
		int bitLength2 = 32 - Integer.numberOfLeadingZeros(bitLength);
		long value = (1<<(bitLength2+1))-2;
		value = (value<<bitLength2) | bitLength;
		if (negative) value<<=1;
		value = (value<<bitLength) | x;
		return new ValueAndBitLength(value, 2*bitLength2+bitLength+(negative?2:1));
	}

	/** Decodes an Elias-encoded integer.
	 *  @param position Index of first bit to be read; e.g. if 63 is given,
	 *                  value is decoded starting from the left end.
	 *  @return Returns the decoded value and the length of the ENCODED value.
	 */
	public static ValueAndBitLength eliasDecode(long value, int position) {
		// bit length of bit length of result
		int bitLength2 = 0;
		while (((value>>>position) & 1) == 1) {
			position-=1;
			bitLength2+=1;
		}
		if (bitLength2==0) return new ValueAndBitLength(0,1);
		position-=1;
		if (position<bitLength2) throw new IllegalArgumentException("Unexpected end of bit sequence.");
		int bitLength = (int)(value>>>(position-bitLength2+1)) & ((1<<bitLength2)-1);
		position-=bitLength2;
		boolean negative = ((value>>>position) & 1) == 0;
		if (negative) position-=1;
		if (position+1<bitLength) throw new IllegalArgumentException("Unexpected end of bit sequence.");
		long result = (value>>>(position-bitLength+1)) & ((1L<<bitLength)-1);
		return negative?new ValueAndBitLength(-result,2*bitLength2+2+bitLength):new ValueAndBitLength(result,2*bitLength2+1+bitLength);
	}

}
